﻿using System.Collections.Generic;
using System.Linq;

namespace Pathfinding
{
    public class Graph<TNode, TEdge>
    {
        public readonly HashSet<TNode> NodeSet = new HashSet<TNode>(); //结点列表
        public readonly Dictionary<TNode, List<TNode>> NeighborList = new Dictionary<TNode, List<TNode>>(); //邻居列表

        public readonly Dictionary<(TNode, TNode), List<TEdge>>
            EdgeList = new Dictionary<(TNode, TNode), List<TEdge>>(); //边列表

        /// <summary>
        /// 寻找指定结点
        /// </summary>
        /// <returns>找到的结点，没找到时返回默认值（引用类型为null）</returns>
        public TNode FindNode(TNode node)
        {
            // 遍历HashSet，查找与目标节点相等的元素
            foreach (var existingNode in NodeSet.Where(existingNode =>
                         EqualityComparer<TNode>.Default.Equals(existingNode, node)))
            {
                return existingNode; // 返回集合中实际存在的实例
            }

            return default; // 未找到时返回默认值（null for 引用类型）
        }

        /// <summary>
        /// 寻找指点起、终点之间直接连接的所有边
        /// </summary>
        /// <param name="source">起点</param>
        /// <param name="target">终点</param>
        /// <returns>找到的边，没找到时返回null</returns>
        public List<TEdge> FindEdge(TNode source, TNode target)
        {
            var s = FindNode(source);
            var t = FindNode(target);
            if (s == null || t == null) return null;
            var nodePairs = (s, t);
            return EdgeList.TryGetValue(nodePairs, out var edge) ? edge : null;
        }

        /// <summary>
        /// 添加结点，用HashSet，包含重复检测
        /// </summary>
        public bool AddNode(TNode node)
        {
            return NodeSet.Add(node);
        }

        /// <summary>
        /// 添加指定边，含空结点判断、重复添加判断
        /// </summary>
        /// <param name="source">边起点</param>
        /// <param name="target">边终点</param>
        /// <param name="edge">指定边</param>
        /// <returns>添加成功与否</returns>
        public bool AddEdge(TNode source, TNode target, TEdge edge)
        {
            var s = FindNode(source);
            var t = FindNode(target);
            if (s == null || t == null)
                return false;
            var nodePairs = (s, t);
            if (!EdgeList.ContainsKey(nodePairs))
            {
                EdgeList.Add(nodePairs, new List<TEdge>());
            }

            var allEdges = EdgeList[nodePairs];
            if (allEdges.Contains(edge)) return false;
            allEdges.Add(edge);
            if (!NeighborList.ContainsKey(source))
            {
                NeighborList.Add(source, new List<TNode>());
            }

            NeighborList[source].Add(target);
            return true;
        }

        /// <summary>
        /// 移除指定结点
        /// </summary>
        /// <returns>移除成功与否</returns>
        public bool RemoveNode(TNode node)
        {
            return NodeSet.Remove(node);
        }

        /// <summary>
        /// 移除指定起、终点的指定边
        /// </summary>
        /// <param name="source">边起点</param>
        /// <param name="target">边终点</param>
        /// <param name="edge">指定边</param>
        /// <returns>移除成功与否</returns>
        public bool RemoveEdge(TNode source, TNode target, TEdge edge)
        {
            var allEdges = FindEdge(source, target);
            return allEdges != null && allEdges.Remove(edge);
        }

        /// <summary>
        /// 移除指定起、终点的所有边
        /// </summary>
        /// <param name="source">边起点</param>
        /// <param name="target">边终点</param>
        /// <returns>移除成功与否</returns>
        public bool RemoveEdgeList(TNode source, TNode target)
        {
            return EdgeList.Remove((source, target));
        }

        /// <summary>
        /// 获取指定结点可抵达的所有邻居结点
        /// </summary>
        public List<TNode> GetNeighbor(TNode node)
        {
            return NeighborList[node];
        }

        /// <summary>
        /// 获取指定结点所延伸出的所有边
        /// </summary>
        public List<TEdge> GetConnectedEdge(TNode node)
        {
            var resEdge = new List<TEdge>();
            var neighbor = GetNeighbor(node);
            foreach (var curEdgeList in neighbor.Select(t => EdgeList[(node, t)]))
            {
                resEdge.AddRange(curEdgeList);
            }

            return resEdge;
        }
    }
}